package com.algrithom.graph.bfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.common.model.Node;

/**
 * @author think
 */
public class BfsOper {
    
    public static void main(String[] args){
        // 迷宫地图
        int[][] maze = new int[][]{{1,0,0,1},{1,1,0,1},{0,1,1,0},{0,0,1,1}};
        bfs(maze);
    }
    
    private static void bfs(int[][] array){
        int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
        int row = array.length;
        int col = array[0].length;
        int[][] visited = new int[row][col];
        List<Node> list = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0,0,-1,-1));
        visited[0][0] = 1;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            list.add(node);
            for (int[] direction : dir) {
                int x = node.getX() + direction[0];
                int y = node.getY() + direction[1];
                
                if (x >= 0 && x < row && y >= 0 && y < col && array[x][y] == 1 && visited[x][y] == 0) {
                    visited[x][y] = 1;
                    queue.offer(new Node(x,y,node.getX(),node.getY()));
                }
            }
        }
        list.forEach(node -> {
            System.out.println("x -> :" + node.getX() + " y -> :" + node.getY());
        });
    }
}
